﻿#pragma once
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BinTreeNode {
    ElemType data;
    struct BinTreeNode* lchild;
    struct BinTreeNode* rchild;
} BinTreeNode;
// 创建二叉树，动态分配内存
BinTreeNode* createTreeNode(ElemType data) {
    BinTreeNode* node = (BinTreeNode*)malloc(sizeof(BinTreeNode));
    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

// 建立二叉树
void createBinaryTree(BinTreeNode** root) {
    *root = createTreeNode('A');
    (*root)->lchild = createTreeNode('B');
    (*root)->rchild = createTreeNode('C');
    (*root)->lchild->lchild = createTreeNode('D');
    (*root)->lchild->rchild = createTreeNode('E');
    (*root)->rchild->rchild = createTreeNode('F');
}

// 前序遍历
void preOrder(BinTreeNode* node) {
    if (node != NULL) {
        printf("%c ", node->data);
        preOrder(node->lchild);
        preOrder(node->rchild);
    }
}

// 中序遍历
void inOrder(BinTreeNode* node) {
    if (node != NULL) {
        inOrder(node->lchild);
        printf("%c ", node->data);
        inOrder(node->rchild);
    }
}

// 后序遍历
void postOrder(BinTreeNode* node) {
    if (node != NULL) {
        postOrder(node->lchild);
        postOrder(node->rchild);
        printf("%c ", node->data);
    }
}

// 返回根节点，打印
int countLeaves(BinTreeNode* node) {
    if (node == NULL) return 0;
    if (node->lchild == NULL && node->rchild == NULL) return 1;
    return countLeaves(node->lchild) + countLeaves(node->rchild);
}

// 释放二叉树空间
void freeBinaryTree(BinTreeNode* node) {
    if (node != NULL) {
        freeBinaryTree(node->lchild);
        freeBinaryTree(node->rchild);
        free(node);
    }
}
void menu() {
    printf("1. 前序遍历\n");
    printf("2. 中序遍历\n");
    printf("3. 后序遍历\n");
    printf("4. 输出叶子数\n");
    printf("5. 释放二叉树空间\n");
    printf("6. ÍË³ö\n");
}

int main() {
    BinTreeNode* root; // 创建根结点
    createBinaryTree(&root); 

    int choice;
    int leavesCount = 0;
    while (1) {
        menu();
        printf("please select: ");
        scanf_s("%d", &choice); 

        switch (choice) {
        case 1:
            printf("前序遍历: ");
            preOrder(root);
            printf("\n");
            break;
        case 2:
            printf("前序遍历: ");
            preOrder(root);
            printf("\n");
            break;
        case 3:
            printf("中序遍历: ");
            inOrder(root);
            printf("\n");
            break;
        case 4:
            printf("后序遍历: ");
            postOrder(root);
            printf("\n");
            break;
        case 5:
        
            leavesCount = countLeaves(root);
            printf("输出叶子结点数: %d\n", leavesCount);
            break;
        
        case 6:
            printf("释放二叉树空间\n");
            freeBinaryTree(root);
            printf("已经释放\n");
            return 0; // ÍË³ö³ÌÐò
        default:
            printf("Wrong\n");
            break;
        }
    }
}